package gr1381.mihailproject;
import java.util.*;

/**
 * @author Mihail Silivonchik, group1381
 * @since 1.02
 * Объект класса <code>Graph<\code> имитирут неориентированный граф.
 * 
 * @param adjacentmatrix матрица смежности
 * @param mNode динамический массив ссылок на объекты класса Node
 * @param time текущее время "глубины" поиска в глубину
 * @param bridges список мостов в String
 */
public class Graph 
{
    /**
     * Конструктор класса
     * @param msize размерность (она же является количество узлов) матрицы смежности
     * @since 1.03
     */
    public Graph (int msize)
    {
        adjacentmatrix = new int [msize][msize];
    }
    
    /**
     * Метод получает количество узлов
     * @return матрицу смежности
     * @deprecated c вводом GUI функция устарела
     * @see gr1381.mihailproject.Graph#Graph(int)
     */
    private int[][] setAdjacentMatrix ()
    {
        Scanner in = new Scanner (System.in); //создаём объект класса Scanner и связываем его со стандартным входным потоком
        System.out.println ("Заполнение матрицы смежности случайными числами");
        System.out.println ("Укажите размерность генерируемой матрицы: ");
        int msize = in.nextInt ();
        int[][] m = new int [msize][msize];
        return m;
        // СОЗДАТЬ НЕРОВНЫЙ МАССИВ?! (прообраз верхней треугольной матрицы смежности)
    }
    
    /**
     * Метод генерирует матрицу смежности, исходя из пожеланий пользователя
     * @since 1.03
     * @deprecated c вводом GUI функция устарела
     * @see gr1381.mihailproject.Graph#randomAdjacentMatrix(int)
     */
    private void randomAdjacentMatrix ()
    {
        Scanner in = new Scanner (System.in); //создаём объект класса Scanner и связываем его со стандартным входным потоком
        
        int i, j;       // индекс столбца-строки
        int saturation; // насыщенность ---
        int maxnode;    // максимальное количество узлов
        int neednode;   // требуемое количество узлов
            
        System.out.println ("Укажите насыщенность генерируемой матрицы: ");
        saturation = in.nextInt ();
        
        maxnode = adjacentmatrix.length-1;
        maxnode = getMaxNode (maxnode);
        neednode = maxnode*saturation/100;
       
        System.out.println ("Заданная насыщенность: " + saturation + " Необходимое количество рёбер: " + neednode + " Максимальное количество рёбер: " + maxnode);
        
        Random generator = new Random ();
        for (; neednode>0; neednode--)
        {
            do
            {
                i = generator.nextInt(adjacentmatrix.length);
                j = generator.nextInt(adjacentmatrix.length);
            }
            while (adjacentmatrix[i][j]==1 || i==j);
            adjacentmatrix[i][j] = 1;
            adjacentmatrix[j][i] = 1;
        }
    }
    
    /**
     * Метод генерирует матрицу смежности, исходя из пожеланий пользователя
     * @since 1.03
     * @param msaturation насыщенность рёбрами
     */
    public void randomAdjacentMatrix (int msaturation)
    {
        int i, j;       // индекс столбца-строки
        int saturation; // насыщенность ---
        int maxnode;    // максимальное количество узлов
        int neednode;   // требуемое количество узлов
            
        saturation = msaturation;
        maxnode = adjacentmatrix.length-1;
        maxnode = getMaxNode (maxnode);
        neednode = maxnode*saturation/100;
        
        System.out.println ("Заданная насыщенность: " + saturation + " Необходимое количество рёбер: " + neednode + " Максимальное количество рёбер: " + maxnode);
        
        Random generator = new Random ();
        for (; neednode>0; neednode--)
        {
            do
            {
                i = generator.nextInt(adjacentmatrix.length);
                j = generator.nextInt(adjacentmatrix.length);
            }
            while (adjacentmatrix[i][j]==1 || i==j);
            adjacentmatrix[i][j] = 1;
            adjacentmatrix[j][i] = 1;
        }
        
        showAdjacentMatrix ();
    }
    
    /**
     * Метод рекурсивно рассчитывает количество рёбер, максимальное для заданного количества вершин
     * (максимальное количество рёбер = количество единичек в "верхнем" треугольнике)
     * @param value КоличествоВершин
     * @return максимальное количество вершин
     */
    private static int getMaxNode (int value)
    {
        if (value>1)
            return value + getMaxNode (value-1);
        else
            return value;
    }
    
    /**
     * Метод преобразует матрицу смежности в строкове представление
     * @since 1.04
     * @return матрица смежности в виде строки
     */
    public String convertToStringAdjacentMatrix ()
    {
        String s = "Матрица смежности:\n", s1;
        for (int[] row : adjacentmatrix) 
        {
             s += Arrays.toString(row);
             s += "\n";
        }
        s1 = s.replaceAll(",", "");
   
        return s1;
    }
    
    /**Метод выводит на экран матрицу смежности*/
    private void showAdjacentMatrix ()
    {
        System.out.println ("Сгенерированная матрица:");
        //цикл "for each"
        for (int[] row : adjacentmatrix) 
        {
            for (int column : row)
                System.out.print(column + " ");
            System.out.println();
        }   
    }
    
    /**Метод создаёт массив узлов необходимого количества*/
    public void createNode ()
    {
        for (int i=0; i<adjacentmatrix.length; i++)
            mNode.add (new Node());
    }
    
    /** @return количество узлов матрицы смежности*/
    public int sizeAdjacentMatrix () { return adjacentmatrix.length; }
    
    /**Метод устанавливает списки смежности для каждого узла*/
    public void setAdjacentList ()
    {
        Iterator <Node> iteratorFrom = mNode.iterator();
        for (int i=0; iteratorFrom.hasNext() /*то же самое = i<adjacentmatrix.length*/; i++)
        {
            // "настраиваем" исходную вершину
            Node elementFrom = iteratorFrom.next(); 
            
            Iterator <Node> iteratorTo = mNode.iterator();
            for (int j=0; iteratorTo.hasNext() == true; j++)
            {
                //перебираем все возможные смежные вершины
                Node elementTo = iteratorTo.next(); 
                if (adjacentmatrix[i][j] == 1)
                    elementFrom.addToAdjacntList(j, elementTo);
            }
        }
        
        showAdjacentList ();
    }
    
    /**Метод выводит на экран списки смежности каждого узла*/
    private void showAdjacentList ()
    {
        int i=-1;
        Iterator <Node> iterator = mNode.iterator();
        while (iterator.hasNext())
        {
            Node element = iterator.next();
            i++;
            System.out.println ("Вершина " + i + ".");
            element.showAdjacentList();
        }
    }
    
    /**Метод, выпполняющий поиск мостов*/
    public void findBridges ()
    {
        System.out.println ("Список мостов:");
        bridges = "Список мостов:\n";
        
        Iterator <Node> iterator = mNode.iterator();
        while (iterator.hasNext())
        {
            Node element = iterator.next();
            // если непосещённая вершина, начинается обход в глубину
            if (!element.getUsed())
                depthFirstSearch (element, null);
        }
    }
    
    /**
     * Метод выполняет модифицированный обход в глубину
     * @param top текущий узел
     * @param parent непосредственный предок узла
     */
    private void depthFirstSearch (Node top, Node parent)
    {
        Node to; // следующий узел
        
        // устанавливаем текущий узел как пройденный
        top.setUsedTrue();
        // устанавливаем начальные "временные" параметры для текущего узла
        top.setTimeIn(time);
        top.setLow(time);
        time++;
        
        // проходим по всем смежным узлам текущего узла
        for (int i=0, key=0; i<top.getSizeAdjacentList(); i++, key++)
        {
            while (top.getAdjacentElement(key) == null && key < adjacentmatrix.length)
                key++;
            
            //если ещё не перебрали все возможные узлы
            if (key < adjacentmatrix.length)
            {
                to = top.getAdjacentElement(key);
                //System.out.println("Смежный узел: " + to.getName());

                // если следующая вершина не предок
                //System.out.println ("==Parent? " + to.equals(parent));
                if (!to.equals(parent))
                    // to - непосещённая вершина
                    if (!to.getUsed())
                    {
                        // продолжаем поиск в глубину
                        depthFirstSearch (to, top);
                        if (to.getLow() < top.getLow())
                            top.setLow(to.getLow());
                        if (to.getLow() > top.getTimeIn())
                        {
                            System.out.println("Ребро " + top.getName() + "-" + to.getName());
                            bridges += "Ребро " + top.getName() + "-" + to.getName() + ";\n";
                        }
                    }
                    // to - обратное ребро
                    else
                    {
                        if (to.getTimeIn() < top.getLow())
                            top.setLow(to.getTimeIn());
                    }
            }
        }
    }
    
    /** @since 1.04 @return строковое представление списка мостов / сообщение об отсутствии оных*/
    public String getStringBridges () 
    { 
        if (!bridges.equals("Список мостов:\n"))
            return bridges;
        else
            return "В данном графе мостов нет!";
    }
 
 
    private int[][] adjacentmatrix;
    private ArrayList < Node > mNode = new ArrayList < Node > ();
    private static int time;
    private static String bridges;
}